//
// Created by Lenovo on 2024/2/7.
//
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<bool> st(nums.size(), false);            //st[i]表示第i个位置能后到达
        st[0]= true;
        for(int i=0;i<nums.size();i++){
            if(st[i]){
                for(int j=i+1;j<nums.size()&&j<=i+nums[i];j++){
                    st[j]= true;
                }
            }
        }
        return st[nums.size()-1];
    }

    //改进，贪心版
    bool canJump2(vector<int>& nums) {
        int cover=0;                            //cover表示能覆盖到的最大下标
        for(int i=0;i<=cover;i++){              //i每次移动只能在 cover的范围内移动，
            cover=max(cover,i+nums[i]);         //每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。
            if(cover>=nums.size()-1)
                return true;
        }
        return false;
    }
};